// Thor - High Performance C++ containers and algorithm library.
//
// Copyright (c) 2010 Su Shi. All rights reserved.
//
// Author: Su Shi <carmack.shi [at] gmail.com>

#ifndef THOR_MERGEABLE_HEAP_H_
#define THOR_MERGEABLE_HEAP_H_

namespace thor {
// Abstract class for defining the basic operations.
template<typename T, typename NodeType>
class MergeableHeap {
 public:
  // Trivial Iterator, only support *, ->, ==, !=.
  class Iterator {
   public:
    typedef T* Pointer;
    typedef const T* ConstPointer;
    typedef T& Reference;
    typedef const T& ConstReference;
    typedef NodeType* NodePtr;

    Iterator()
      : node_ptr_(NULL), auto_deleted_(false) { }
    explicit Iterator(NodePtr node_ptr, bool auto_deleted = false)
      : node_ptr_(node_ptr), auto_deleted_(auto_deleted) { }
    virtual ~Iterator() {
      if (auto_deleted_)
        delete node_ptr_;
    }

    virtual Reference operator*() = 0;
    virtual ConstReference operator*() const = 0;

    virtual Pointer operator->() = 0;
    virtual ConstPointer operator->() const = 0;

    bool operator==(const Iterator& right) const {
      return (node_ptr_ == right.node_ptr_);
    }

    bool operator!=(const Iterator& right) const {
      return !(*this == right);
    }

    friend class MergeableHeap<T, NodeType>;

   protected:
    NodePtr node_ptr_;
    bool auto_deleted_;
  };

  virtual ~MergeableHeap() { }

  // Mergeable Heap supported five basic operations.
  MergeableHeap();
  virtual void Insert(const T&) = 0;
  virtual Iterator Minimum() const = 0;
  virtual void ExtractMinimum() = 0;
  virtual void Union(MergeableHeap<T, NodeType>* heap) = 0;
  virtual void DecreaseKey(Iterator& it, const T& key) = 0;
  virtual void Delete(Iterator it) = 0;
};

}  // namespace thor

#endif  // THOR_MERGEABLE_HEAP_H_
